Radix Sort

최댓값의 자릿수를 알고 있을때 굉장히 빠르게 정렬할 수 있다.

10개의 원소에 0에서부터 9까지의 번호를 부여한다.
일의 자릿수 값만을 보고 각 데이터들을 정렬한다.
십의 자릿수 값만을 보고 각 데이터들을 정렬한다.
백의 자릿수 값만을 보고 각 데이터들을 정렬한다
...
이를 최대 자릿수까지 수행한다.

이 때, 하나의 원소에 여러개의 데이터가 들어갈 경우, 최근에 들어온 데이터를 아래에 배치한다. 즉, 하나의 원소 내부에 위 아래 위계가 갈린다.

'0번', '위'부터 읽으면 끝.

시간복잡도는 O(n)이다.